L-Systems
L-systems 'is a technique for iteratively creating a structure from a starting pattern and a list of replacement rules. First introduced in 1968 by Aristid Lindenmeyer, they were originally intended to simulate the development of multicellular organisms. They are commonly used to simulate plants, but can be applied for generating cities, buildings, and other things. L-Systems Algorithm Two types of L-systems are shown here. The first is a simple, generic replacement algorithm. The second include parameters in the rules, which results in different outputs depending on the values of the variables. Generic Algorithm rules = { 'a': 'b', 'b': 'ab' } iterations = 5 start = 'aaaaa' end = '' for x in range(0,iterations): for y in start: if rulesy: end = end + rulesy start = end end = '' Generic Algorithm Explained What's shown above is a very general way of implementing L-systems in Python. The '''rules '''dictionary contains ''production rules. In the input string, anywhere the key is found, it's replaced with the value. '''start is the input, end'' ''is the eventual output. iterations is how many times you wish to check the input string for the rules to match with. The output of the generic algorithm would look similar to this: aaaaa bbbbb ababababab babbabbabbabbab abbababbababbababbababbab bababbabbababbabbababbabbababbabbababbab L-systems are relatively easy in design. Part of the challenge lies in providing both interesting input and ''interesting production rules. Generic Algorithm with Parameters rules = { 'a(x,y): x < 3 -> b(x+y)', 'b(y): y <= 3 -> a(y)', 'b(y): y > 3 -> a(y+1)' } iterations = 5 start = 'a(1,1)b(1)b(5)' end = '' for x in start: if x in rules: end = end + rulesx start = end end = '' Generic Algorithm with Parameters Explained This is another general way of implementing L-systems. The difference here is that each production rule also has one or more parameters. Production rules can be thought of simple functions in a programming language. They only have one conditional, and output the string to replace them with, where the variables are replaced as necessary. For example, '''a(1,1) '''would output '''b(2)'. Parameters allow for more control and variety in what is outputted. Case Studies Plant Development Simulation The classical use of L-systems is simulating plant growth. It's been noticed that plants grow in a way that is self-repeating. Typically this is in the form of branches growing off of branches, which in turn come from larger branches, and so on. There is also a repeated behavior for growth: a new branch buds, turns into a flower, grows a fruit, and eventually dies. Because plants repeat themselves in such a fashion, they can be modeled with L-systems. Their production rules can range from simple to complex, giving plants their varied appearances. CityEngine CityEngine is a software tool that procedurally generates cities given statistical and geographical data, such as population density, elevation, and so on. L-systems are used in two ways. First, road networks are generated based on the population density provided. Main roads are created, connected with less important streets, and areas of dense population are connected with highways. The second use of L-systems is generating buildings. Buildings come in the form of skycrapers, commercial buildings, and residential buildings. Each of these types has its own set of production rules. Code Examples Here two code examples are given. The first shows how make a plant using L-systems. The second is a simple town generator. Both are found in the lsystem folder of the repository. Plant Example This example demonstrates how plants are self-similar enough that they can be modeled using two rewrite rules. Town Example This example uses a parameterized L-system to make a small town, where buildings are represented by colored squares and rectangles. Black squares are houses, red rectangles are schools, green rectangles are shops, blue rectangles are churches, and grey rectangles are town halls. See if you can change the starting condition and the number of iterations to make an interesting output! Citations * Parish, Yoav I. H. and Pascal Müller. 2001. "Procedural modeling of cities. In Proceedings of the 28th annual conference on Computer graphics and interactive techniques (SIGGRAPH '01). ACM, New York, NY, USA, 301-308. DOI=http://dx.doi.org/10.1145/383259.383292 * Prusinkiewicz, Przemyslaw and Mark Hammel and Jim Hanan and Radomír Mech. L-Systems: From The Theory To Visual Models Of Plants. 1996. http://algorithmicbotany.org/papers/sigcourse.2003/2-1-lsystems.pdf